According to a first conventional method, a product of an unsigned multiplication A[5:xe2x88x922]xc3x97B[5:xe2x88x922] (e.g., 0,000 00.012xc3x971,01010.102 or 0.2510xc3x9742.510) is obtained and added to an accumulator value T[15:0] (e.g., 0,00000,00010,00000.2=64.10) as follows.
The two values A[5:xe2x88x922] and B[5:xe2x88x922] are received by an 8xc3x978 carry save multiplier that produces a 16-bit sum value S[11:xe2x88x924] and a 16-bit carry value C[11:xe2x88x924]. The sum and carry bits S[xe2x88x921:xe2x88x924] and C[xe2x88x921:xe2x88x924] that are less significant than the bits of the accumulator value T[15:0] are discarded. The sum and carry values S[11:0] and C[11:0] are extended with zero""s to form values S[15:0] and C[15:0] to match the bit weights of the register value T[15:0]. Subsequently, the values S[15:0] and C[15:0] are added to register value T[15:0].
A problem with this first conventional method is that an unwanted carry out often occurs when adding sum and carry values generated by some methods such as booth recoding. Accordingly, a second conventional method of multiplying A[5:xe2x88x922]xc3x97B[5:xe2x88x922] which eliminates the unwanted carry out has been developed.
Specifically, the two values A[5:xe2x88x922] and B[5:xe2x88x922] are received by an 8xc3x978 booth recoded carry save multiplier that produces a 16-bit sum value S[11:xe2x88x924] (e.g., 00,00000,10011.00102=19.12510) and a 16-bit carry value C[11:xe2x88x924] (e.g., 11,11111,10111.10002=4087.510 unsigned=xe2x88x928.510 signed). The two values S[11:xe2x88x924] and C[11:xe2x88x924] are added in a 2:1 adder in a first stage to form a product P[11:xe2x88x924] (e.g., 00,00000,01010.10102=10.62510). The unwanted carry out is eliminated during this 2:1 addition by discarding the most significant carry bit.
Bits P[xe2x88x921:xe2x88x924] are also discarded and bits P[15:12] are assigned values of 0 to form product P[15:0] (e.g., 0,00000,00000,010102=1010) thereby matching the bit weights of accumulator value T[15:0]. The product value P[15:0] is added to the accumulator value T[15:0] in a 2:1 adder in a second stage to form a result value Txe2x80x2[15:0] (e.g., 0,00000,00010,010102=7410)
This two stage addition requires a booth recoded carry save multiplication followed by two additions in series using relatively slow 2:1 adders. Therefore, what is desired is a faster circuit and method for performing a booth multiplication (and adding the product to a third (e.g., accumulator) value.
A carry save multiplier receives two input values having respective bit lengths A and B and provides sum and carry values, each having bit lengths A+B+1. A carry prediction circuit receives the most significant bit of the sum and carry values and provides an extension bit to be merged with less significant bits of the sum and carry values. A carry save adder receives the altered sum and carry values, as well as a third input value to provide second sum and carry values.
In one embodiment, the second sum and carry values are added in a carry propagate adder to form a resulting value. In one embodiment, the carry prediction circuit is an XOR gate that receives the most significant bit of the first sum and carry values. In another embodiment, the circuit is an OR gate that receives the most significant bits and outputs the extension bit to be merged with the less significant bits of at least one of the first sum and first carry bits.
The present invention provides a faster circuit and method for performing a multiplication and adding the product to a third (e.g., accumulator) value.